The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(O(1), O(n^1)).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

a(a(x1)) → b(b(b(x1)))
a(x1) → c(d(x1))
b(b(x1)) → c(c(c(x1)))
c(c(x1)) → d(d(d(x1)))
e(d(x1)) → a(b(c(d(e(x1)))))
b(x1) → d(d(x1))
e(c(x1)) → b(a(a(e(x1))))
c(d(d(x1))) → a(x1)

Rewrite Strategy: INNERMOST

(1) CpxTrsMatchBoundsProof (EQUIVALENT transformation)

A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 4.
The certificate found is represented by the following graph.

Start state: 1271
Accept states: [1272, 1273, 1274, 1275]
Transitions:
1271→1272[a_1|0, a_1|1]
1271→1273[b_1|0]
1271→1274[c_1|0, a_1|1]
1271→1275[e_1|0]
1271→1271[d_1|0]
1271→1276[d_1|1]
1271→1277[d_1|1]
1271→1278[e_1|1]
1271→1282[d_1|2]
1276→1272[c_1|1]
1277→1273[d_1|1]
1278→1279[d_1|1]
1279→1280[c_1|1]
1280→1281[b_1|1]
1280→1283[d_1|2]
1280→1275[a_1|3]
1280→1278[a_1|3]
1280→1285[d_1|4]
1281→1275[a_1|1]
1281→1278[a_1|1]
1281→1284[d_1|2]
1282→1274[c_1|2]
1282→1272[c_1|2]
1283→1281[d_1|2]
1283→1275[a_1|3]
1283→1278[a_1|3]
1283→1285[d_1|4]
1284→1275[c_1|2]
1284→1278[c_1|2]
1285→1275[c_1|4]
1285→1278[c_1|4]

(2) BOUNDS(O(1), O(n^1))